package cn.edu.xjtu.work.addBinary;

/**
 * 67. 二进制求和
 * 
 * 给你两个二进制字符串，返回它们的和（用二进制表示）。
 * 
 * 输入为非空字符串且只包含数字 1 和 0。
 */
public class Solution {
  public static void main(String[] args) {
    String a = "1";
    String b = "111";
    addBinary(a, b);
  }

  /**
   * 直接相加,先找出a,b中最短的将其全部加完,然后再将另外一个没有加完的加在结果前面
   * 
   * @param a
   * @param b
   * @return
   */
  public static String addBinary(String a, String b) {
    int lenA = a.length() - 1;
    int lenB = b.length() - 1;
    StringBuilder sb = new StringBuilder();
    int carry = 0;
    int n = Math.min(lenA, lenB);

    for (int i = 0; i <= n; i++) {
      int s = a.charAt(lenA--) - '0' + b.charAt(lenB--) - '0' + carry;
      if (s == 0 || s == 1) {
        carry = 0;
        sb.insert(0, s);
      } else {
        carry = 1;
        sb.insert(0, s - 2);
      }
    }
    if (lenA < 0) {
      a = b;
      lenA = lenB;
    }
    n = lenA;
    for (int i = 0; i <= n; i++) {
      int s = a.charAt(lenA--) - '0' + carry;
      if (s == 0 || s == 1) {
        carry = 0;
        sb.insert(0, s);
      } else {
        carry = 1;
        sb.insert(0, s - 2);
      }
    }
    if (carry == 1) {
      sb.insert(0, 1);
    }
    return sb.toString();
  }
}
